package summer.hot100;

import java.util.ArrayList;
import java.util.List;

public class Solution438 {
    public List<Integer> findAnagrams(String s, String p) {
        int[] hashP = new int[26];
        for (int i = 0; i < p.length(); i++) {
            hashP[p.charAt(i) - 'a']++;
        }
        int[] hashS = new int[26];
        int i = 0;
        int j = 0;
        List<Integer> res = new ArrayList<>();
        while (i < s.length()) {
            char cur = s.charAt(i);
            hashS[cur - 'a']++;
            while (j < s.length() && hashS[cur - 'a'] > hashP[cur - 'a']) {
                hashS[s.charAt(j) - 'a']--;
                j++;
            }
            if (i - j + 1 == p.length()) res.add(j);
            i++;
        }
        return res;
    }
}
